#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

namespace Mypriority_queue{
    //仿函数/函数对象
    //这个类可以像函数一样使用
    //用来控制建大堆
    template<class T>
    class less{
    public:
        bool operator()(const T& x,const T& y){
            return x<y;
        }
    };

    //用来控制建小堆
    template<class T>
    class greater{
    public:
        bool operator()(const T& x,const T& y){
            return x>y;
        }
    };

    //模版参数container用来做适配器，comapre用来控制建堆
    template<class T,class container=vector<T>,class comapre=less<T>>
    class priority_queue{
    private:
        //向下调整
        void AdjustDown(size_t parents){
            comapre com;
            //向下调整，由父节点找子节点，父节点乘2再加1
            size_t child=parents*2+1;
            if(child+1<_con.size()&&com(_con[child],_con[child+1])){
                child++;
            }
            while(child<_con.size()){
                if(com(_con[parents],_con[child])){
                    swap(_con[parents],_con[child]);
                    parents=child;
                    child=parents*2+1;
                }
                else{
                    break;
                }
            }
        }

        //向上调整
        void AdjustUp(size_t child){
            comapre com;
            //向上调整，由子节点找父节点，子节点先-1再除2
            size_t parents=(child-1)/2;
            while(child>0){
                if(com(_con[parents],_con[child])){
                    swap(_con[parents],_con[child]);
                    child=parents;
                    parents=(child-1)/2;
                }
                else{
                    break;
                }

            }
        }
    public:
        //模版参数用来表示对应T类型的迭代器类型
        template<class InputIterator>
        priority_queue(InputIterator first,InputIterator last){
            while(first!=last){
                _con.push_back(*first);
                first++;
            }
            //向下调整建堆
            //注意，for循环中，i最好不要用size_t,如果出现i小于0时，会死循环
            for(int i=(_con.size()-1-1)/2;i>=0;i--){
                AdjustDown(i);
            }
        }

        void pop(){
            swap(_con[0],_con[_con.size()-1]);
            _con.pop_back();
            AdjustDown(0);
        }

        void push(const T& x){
            _con.push_back(x);
            AdjustUp(_con.size()-1);
        }

        T& top(){
            return _con[0];
        }

        const T& top()const {
            return _con[0];
        }

        size_t size()const {
            return _con.size();
        }

        bool empty()const {
            return _con.empty();
        }

    private:
        container _con;

    };




}